package ljl.codetop;

import commons.ListNode;

/**
 * 这个题，难，直接放弃尝试
 */
public class _148_sort_list {

    static class have_a_try {

        // 他让常数空间复杂度，nlogn 时间复杂度，我日？这是什么东西，怎么做到？
        public ListNode sortList(ListNode head) {
            return null;
        }
    }

    /**
     * 这个用了递归，所以空间不是 O(1)
     */
    static class lufei {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode fast = head.next, slow = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode tmp = slow.next;
            slow.next = null;
            ListNode left = sortList(head);
            ListNode right = sortList(tmp);
            ListNode h = new ListNode(0);
            ListNode res = h;
            while (left != null && right != null) {
                if (left.val < right.val) {
                    h.next = left;
                    left = left.next;
                } else {
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            h.next = left != null ? left : right;
            return res.next;
        }
    }

    static class copy_lufei1 {

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode tail = slow.next;
            slow.next = null;
            ListNode left = sortList(head);
            ListNode right = sortList(tail);
            ListNode dummy = new ListNode(0);
            ListNode p = dummy;
            while (left != null && right != null) {
                if (left.val < right.val) {
                    p.next = left;
                    left = left.next;
                }
                else {
                    p.next = right;
                    right = right.next;
                }
                p = p.next;
            }
            p.next = left == null ? right : left;
            return dummy.next;
        }
    }

    /**
     * 结合官方和路飞的解法，给出的一个比较优化且容易理解的版本
     */
    static class lufei2 {

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            int length = 0;
            ListNode node = head;
            while (node != null) {
                length++;
                node = node.next;
            }
            ListNode dummyHead = new ListNode(0, head);
            for (int subLength = 1; subLength < length; subLength <<= 1) {
                ListNode prev = dummyHead, curr = dummyHead.next;
                while (curr != null) {
                    ListNode head1 = curr;
                    for (int i = 1; i < subLength && curr.next != null; i++) {
                        curr = curr.next;
                    }
                    ListNode head2 = curr.next;
                    curr.next = null;
                    curr = head2;
                    for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                        curr = curr.next;
                    }
                    ListNode next = null;
                    if (curr != null) {
                        next = curr.next;
                        curr.next = null;
                    }
                    while (head1 != null && head2 != null) {
                        if (head1.val < head2.val) {
                            prev.next = head1;
                            head1 = head1.next;
                        } else {
                            prev.next = head2;
                            head2 = head2.next;
                        }
                        prev = prev.next;
                    }
                    prev.next = head1 == null ? head2 : head1;
                    while (prev.next != null) {
                        prev = prev.next;
                    }
                    curr = next;
                }
            }
            return dummyHead.next;
        }
    }

    static class copy_lufei2 {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            int len = 0;
            for (ListNode p = head; p != null; p = p.next)
                len++;
            ListNode dummy = new ListNode(0, head);
            for (int step = 1; step < len; step <<= 1) {
                ListNode prev = dummy, cur = dummy.next;
                while (cur != null) {
                    ListNode head1 = cur;
                    for (int i = 1; i < step && cur.next != null; i++) {
                        cur = cur.next;
                    }
                    ListNode head2 = cur.next;
                    cur.next = null;
                    cur = head2;
                    for (int i = 1; i < step && cur != null && cur.next != null; i++) {
                        cur = cur.next;
                    }
                    ListNode next = null;
                    if (cur != null) {
                        next = cur.next;
                        cur.next = null;
                    }
                    while (head1 != null && head2 != null) {
                        if (head1.val < head2.val) {
                            prev.next = head1;
                            head1 = head1.next;
                        } else {
                            prev.next = head2;
                            head2 = head2.next;
                        }
                        prev = prev.next;
                    }
                    prev.next = head1 == null ? head2 : head1;
                    while (prev.next != null)
                        prev = prev.next;
                    cur = next;
                }
            }
            return dummy.next;
        }
    }
}
